package org.liaohailong.helloworld.sort;

/**
 * Author: liaohailong
 * Time: 2021/8/2 16:23
 * Describe: 计数排序
 */
public class CountSort implements ISort {

    @Override
    public void sort(int[] arr) {
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i : arr) {
            if (i > max) max = i;
            else if (i < min) min = i;
        }

        int count = max - min + 1;
        int[] counter = new int[count];
        // 计数
        for (int i : arr) counter[i - min]++;

        int index = 0;
        int _index = 0;
        while (index < counter.length) {
            while (counter[index]-- > 0) {
                arr[_index] = index + min;
                _index++;
            }
            index++;
        }
    }
}
